#include  <cstdio>

void find_max_right(int *arr, int *res, int n)
{
	res[n-1] = arr[n-1];
	for( int i = n-2 ; i > -1 ; --i )
		res[i] = res[i+1] > 0 ? arr[i] + res[i+1] : arr[i];
}

void find_max_left(int *arr, int *res, int n)
{
	res[0] = arr[0];
	for( int i = 1 ; i < n ; ++i )
		res[i] = res[i-1] > 0 ? arr[i] + res[i-1] : arr[i];
}

int find_max(int *arr, int n)
{
	int max = arr[0];

	for( int i = 0 ; i < n ; ++i )
		if( arr[i] > max ) 
			max = arr[i];

	return max;
}

int main(int argc, char *argv[])
{
	int cases;
	scanf("%d",&cases);

	for( int i = 0 ; i < cases ; ++i )
	{
		int n;
		scanf("%d",&n);
		int arr[50000];
		int left[50000],right[50000];

		for( int i = 0 ; i < n  ; ++i )
			scanf("%d",&arr[i]);

		find_max_left(arr,left,n);
		find_max_right(arr,right,n);
	
		int max_left = left[0];
		int max_right = find_max(right+1,n-1);
		int max = max_left + max_right;
		
		for( int i = 2 ; i < n - 1 ; ++i )
		{
			if(right[i-1] == max_right)
				max_right = find_max(right+i,n-i);

			if(left[i-1] > max_left)
				max_left = left[i-1];

			int temp = max_left + max_right;
			max = temp > max ? temp : max;
		}
		
		printf("%d\n",max);
	}
	
}
